package lcr;

import java.util.Deque;
import java.util.LinkedList;

public class Test0038 {

    public static void main(String[] args) {
        new Solution0038_1().dailyTemperatures(new int[]{73,74,75,71,69,72,76,73});
    }

}


class Solution0038_1 {
    public int[] dailyTemperatures(int[] temperatures) {
        int l=0,r=1;
        int length = temperatures.length;
        Deque<Integer> stack = new LinkedList<>();
        stack.offer(0);

        for (; r < length; r++){
            while (!stack.isEmpty()&&temperatures[stack.peek()]<temperatures[r]) {
                Integer poll = stack.poll();
                temperatures[poll]=r-poll;
            }

            stack.offer(r);
        }

        while (!stack.isEmpty())  temperatures[stack.poll()]=0;

        return temperatures;
    }
}